Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

如果 s1 的排列之一是 s2 的子字串，則傳回 true。

Example 1

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Step

1. 先將 s1 字串中的 chart 建立一個 hash table
   

2. 將 s2 字串以 s1 長度為基準將 s2 的 chart 也建立 hash table
   

3. 可以看到 s2 的 hash table 中的內容和 s1 hash table 中的不一樣，所以 sliding window 往右邊移動一格（移除 s2 的 index = 0 並加入 s2 的 index = 4）
   

4. 繼續比對，s2 的 hash table 中的內容和 s1 hash table 中的不一樣，所以 sliding window 往右邊移動一格（移除 s2 的 index = 1 並加入 s2 的 index = 5）
   

5. 繼續比對，s2 的 hash table 中的內容和 s1 hash table 中的不一樣，所以 sliding window 往右邊移動一格（移除 s2 的 index = 2 並加入 s2 的 index = 6）
   

6. 繼續比對，s2 的 hash table 中的內容和 s1 hash table 中的不一樣，所以 sliding window 往右邊移動一格（移除 s2 的 index = 3 並加入 s2 的 index = 7）
   

現在 s2 的 hash table 中的內容和 s1 hash table 中的一樣，於是回傳 true。

Coding

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function(s1, s2) {
    const hash = new Map();

    for (let i = 0; i < s1.length; i++) {
        if (!hash.has(s1[i])) hash.set(s1[i], 1);
        else hash.set(s1[i], hash.get(s1[i]) + 1);
    }

    let l = 0, r = 0;
    const s2Hash = new Map();
    while (r < s2.length) {
        let range = r - l + 1;
        if (!s2Hash.has(s2[r])) s2Hash.set(s2[r], 1);
        else s2Hash.set(s2[r], s2Hash.get(s2[r]) + 1);

        if (range === s1.length) {
            let match = true
            for (const [key, count] of hash.entries()) {
                if (!s2Hash.has(key) || s2Hash.get(key) !== count) match = false
            }
            if (match) {
                return true
            }

            const lItem = s2Hash.get(s2[l]) - 1;
            if (lItem === 0) s2Hash.delete(s2[l]);
            else s2Hash.set(s2[l], lItem);
            l++;
        }
        r++;
    }
    return false;
};

Time complexity: O(n)